Integer Factorisation program
I wrote an integer factorisation program (Java bytecode also available for those without a compiler) using an algorithm I just made up, and it works surprisingly well (significantly better than brute force, not nearly as good as the best-known algorithms out there today). Yes, it still has exponential running time, but I thought it was a neat idea.
Here’s the gist of the algorithm: let the factors you hope to generate be called A and B. Choose which of their bits is the most significant 1 in such a way that the target number we want to factor is between A and B’s minimum and maximum products. That is to say, if we filled the rest of the bits in A and B with zeros, their product will be too small, but if we filled them with ones, their product will be too big. Now, recursively try making the most significant bit 0, and try making it 1. If we ever get a situation in which the target number is out of our range (either our minimum product is too big or our maximum product is too small), don’t bother investigating further. If you can’t find any factors, choose different lengths for the original A and B (iterate over the entire space of valid factor lengths). Naturally, I assume that both A and B are odd (since this would be trivial if one of the factors were even), and make their least significant bits 1 as well.
The way this program is set up, you specify the number of bits in the factors on the command line (so the number it will factor has roughly twice as many bits). It generates 2 random prime factors of the requested length, multiplies them together, and prints all that out. It then uses the algorithm to re-find the factors, and prints out the factors as well as the number of steps it took to find them. On Knuth (the main computer in the HMC Computer Science department), I can factor 64-bit numbers (by specifying 32 on the command line) in about 15 minutes. Nifty!
Here’s the thing: I just made this up. I have no idea if it’s a well-known algorithm. Moreover, I can’t figure out a tighter theoretical bound on its running time than O(√3n) (which is slower than the brute-force method at O(√2n)), even though it empirically performs better than brute force for large-ish n (for n≈30, it’s probably “O(1.3n)”). Any insights would be welcome.
(for n≈30, it’s probably O(1.3n))
What on earth does that mean?!
Perhaps I should have used Reid’s “O()” notation. I have no insight into the actual running time of the algorithm outside of O(2n). For small n (4-10), you really can’t empirically tell what the running time is, since it’s all over the place for different factors. As n increases, the running time evens out. For n in the 26-32 range (which, in hindsight, should be the 52-64 range due to how my input works), its behavior seemed pretty close to O(1.3n). I haven’t had the patience to test it for n much higher than that, so I don’t know if this actually continues.
Again, I have no proof of this; it’s just the behavior I observed, at the ranges of n where I observed it.